package com.zsj.Tree;

import lombok.Data;

/**
 * @Author zsj
 * @Version 1.0
 * @Date 2024/4/14 14:11
 * @Description 二叉搜索树
 */
@Data
public class BinarySearchTreeAnyType<E extends Comparable<E>, V> {


    public BSNode<E, V> root;//根节点


    public static class BSNode<E, V> {
        E key;
        V value;
        BSNode<E, V> left;
        BSNode<E, V> right;

        public BSNode(E key) {
            this.key = key;
        }

        public BSNode(E key, V value, BSNode<E, V> left, BSNode<E, V> right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }

        public BSNode(E key, V value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public String toString() {
            return value.toString();
        }
    }

    /**
     * 根据key来搜索值
     *
     * @param key key
     * @return 返回的对象值
     */
    public Object get(E key) {
        BSNode<E, V> cur = root;
        while (cur != null) {
            /*
              compareTo 有三种返回值
              -1 是key < cur.key
              0 key = cur.key
              1 key > cur.key
             */
            int result = key.compareTo(cur.key);
            if (result < 0) {
                cur = cur.left;
            } else if (result > 0) {
                cur = cur.right;
            } else return cur.value;
        }
        return null;
    }


    /**
     * 搜最小值   最左边的叶子节点就是最小的
     *
     * @return 最小值
     */
    public Object min() {
        BSNode<E, V> cur = root;
        while (cur.left != null) {
            cur = cur.left;
        }
        return cur;
    }


    /**
     * 搜最大值 最右边的叶子节点就是最大的
     *
     * @return 最大值
     */
    public Object max() {
        return null;
    }

    /**
     * 往树中添加值
     *
     * @param key   key
     * @param value 值
     * @return 添加结果
     */
    public boolean put(int key, Object value) {
        return true;
    }

    /**
     * 查找关键字的前驱值
     *
     * @param key 关键字
     * @return 前驱值
     */
    public Object successor(int key) {
        return null;
    }

    /**
     * 查找关键字的后驱值
     *
     * @param key 关键字
     * @return 后驱值
     */
    public Object predecessor(int key) {
        return null;
    }

    /**
     * 根据关键字进行删除
     *
     * @param key 关键字
     * @return 对应节点值
     */
    public Object delete(int key) {
        return null;
    }

}

